// to compile: g++ -I/opt/local/include cards.cpp

#include <iomanip>
#include <iostream>
#include <limits>
#include <map>

#include <assert.h>
#include <math.h>

//#define DEBUG
#define TAB 3
#define MAX_RED 27
#define MAX_BLACK 27
#define CUTOFF 1000

#define TABS(n)								\
  std::setw(TAB) << std::setfill('-') << n << std::setw(n * TAB) << std::setfill(' ') << ' ' \

typedef std::map<std::size_t, std::size_t> BetMap;

std::size_t
find_opt_profit(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t dfs_level);

BetMap* betmap[MAX_RED][MAX_BLACK];

std::size_t counter = 0; // count how many recursive calls we make
std::size_t cache_hits = 0; // count number of cache hits
std::size_t cutoff = 0; // count number of cutoff


std::size_t
opt_profit(std::size_t no_red, std::size_t no_black, std::size_t pocket)
{
  BetMap* bm = betmap[no_red][no_black];
  BetMap::const_iterator bm_it = bm->find(pocket);

  if (bm_it != bm->end())
    {
#ifdef DEBUG
      std::cerr << "read_opt_profit(" << no_red << ", " << no_black << ", " << pocket << ") = " << bm_it->second << std::endl;
#endif
      return bm_it->second;
    }

  return 0;
}


void
set_opt_profit(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t opt_profit)
{
  BetMap* bm = betmap[no_red][no_black];
  BetMap::const_iterator bm_it = bm->find(pocket);

#ifdef DEBUG
  std::cerr << "set_opt_profit(" << no_red << ", " << no_black << ", " << pocket  << ", " << opt_profit << ")" << std::endl;
#endif

  assert (bm_it == bm->end());

  bm->insert(std::make_pair<std::size_t, std::size_t>(pocket, opt_profit));
}


std::size_t
try_bet(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t best_guarantee_sofar, 
	std::size_t bet_amount, std::size_t dfs_level)
{
  std::size_t this_guarantee;
  std::size_t local_guarantee;

#ifdef DEBUG
  std::cerr << TABS(dfs_level) << "bet_amount = " << bet_amount << std::endl;
#endif

  // this case has not been investigated yet.
  // we bet for BLACK in this case.
#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"Nothing cached. Check 2 possibilities" << std::endl;
#endif	  
  local_guarantee = std::numeric_limits<std::size_t>::max();
  
  // 2 POSSIBILITIES
  // (1) the revealed card is red and we lose some money
  this_guarantee = find_opt_profit(no_red-1, no_black, pocket - bet_amount, dfs_level+1);

  assert (this_guarantee > 0);
  
#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"If get RED, this_guarantee = " << this_guarantee << std::endl;
#endif

  if (local_guarantee > this_guarantee)
    {
      local_guarantee = this_guarantee;
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"Update local_guarantee = " << this_guarantee << std::endl;
#endif
    }
  
  // (2) the revealed card is black and we win some money. 
  this_guarantee = find_opt_profit(no_red, no_black-1, pocket + bet_amount, dfs_level+1);

  assert (this_guarantee > 0);

#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"If get BLACK, this_guarantee = " << this_guarantee << std::endl;
#endif
      
  if (local_guarantee > this_guarantee)
    {
      local_guarantee = this_guarantee;
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"Update local_guarantee = " << this_guarantee << std::endl;
#endif
    }
  else
    {
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"No need to update local_guarantee, still = " << local_guarantee << std::endl;
#endif
    }
  
  return local_guarantee;
}

std::size_t
binary_bet_search(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t dfs_level)
{
  std::size_t best_guarantee = 0;

  std::size_t beg = 0;
  std::size_t end = pocket - 1;

  std::size_t mid;
  std::size_t after_mid;
  std::size_t mid_profit;
  std::size_t after_mid_profit;

#ifdef DEBUG
  std::cerr << TABS(dfs_level) << "start binary search" << std::endl;
#endif

  if (beg == end)
    {
      best_guarantee = try_bet(no_red, no_black, pocket, best_guarantee, end, dfs_level);
    }

  while (beg != end)
    {
      mid = (beg + end) / 2;
      after_mid = mid+1;

#ifdef DEBUG
      std::cerr << TABS(dfs_level) << "mid = " << mid << ", beg = " << beg << ", end = " << end << std::endl;
#endif

      mid_profit = try_bet(no_red, no_black, pocket, best_guarantee, mid, dfs_level);
      if (mid_profit > best_guarantee)
	{
	  best_guarantee = mid_profit;
	}

      after_mid_profit = try_bet(no_red, no_black, pocket, best_guarantee, after_mid, dfs_level);
      if (after_mid_profit > best_guarantee)
	{
	  best_guarantee = after_mid_profit;
	}

      if (after_mid_profit > mid_profit)
	{
	  beg = after_mid;
	}
      else
	{
	  end = mid;
	}
#ifdef DEBUG
      std::cerr << TABS(dfs_level) << "mid_profit = " << mid_profit << ", after_mid_profit = " << after_mid_profit << std::endl;
      std::cerr << TABS(dfs_level) <<"beg = " << beg << ", end = " << end << std::endl;
#endif
    }

#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"CAN PUT TO CACHE HERE NoRed = " << no_red << ", NoBlack = " << no_black << ". Pocket = " << pocket << std::endl;
#endif 
  
  set_opt_profit(no_red, no_black, pocket, best_guarantee);
  return best_guarantee;
}


std::size_t
linear_bet_search(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t dfs_level)
{
  std::size_t best_guarantee = 0;
  std::size_t local_guarantee;
  std::size_t previous_guarantee = 0;

  //std::size_t k = max_bet(no_red, no_black, pocket);
  std::size_t k = pocket - 1;
#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"Max Bet = " << k << std::endl;
#endif 

  for (std::size_t i = 0; i <= k; i++)
    { // try safe bets (up to k)

#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"Checking(" << no_red << ", " << no_black << ", " << pocket << ") with Bet = " << i << std::endl;
#endif 

      local_guarantee = try_bet(no_red, no_black, pocket, best_guarantee, i, dfs_level);

      if (local_guarantee > best_guarantee)
	{
	  
#ifdef DEBUG
	  std::cerr << TABS(dfs_level) <<"Update best_guarantee = " << best_guarantee;
#endif
	  best_guarantee = local_guarantee; // meaning that we choose to bet i
	  
#ifdef DEBUG
	  std::cerr  <<" to " << best_guarantee << std::endl;
#endif
	}
      
      if (local_guarantee < previous_guarantee)
	{
#ifdef DEBUG
	  std::cerr << TABS(dfs_level) << "Break because opt_profit starts decreasing" << std::endl;
#endif
	  break;
	}
      else
	{
	  previous_guarantee = local_guarantee;
	}
      
    }

#ifdef DEBUG
  std::cerr << TABS(dfs_level) <<"CAN PUT TO CACHE HERE NoRed = " << no_red << ", NoBlack = " << no_black << ". Pocket = " << pocket << std::endl;
#endif 

  return best_guarantee;
}

std::size_t
find_opt_profit(std::size_t no_red, std::size_t no_black, std::size_t pocket, std::size_t dfs_level)
{
#ifdef DEBUG
  std::cerr << TABS(dfs_level) << "find_opt_profit()" << std::endl;
  std::cerr << TABS(dfs_level) <<"CAN QUERY CACHE HERE NoRed = " << no_red << ", NoBlack = " << no_black << ". Pocket = " << pocket << std::endl;
#endif

  if (pocket > CUTOFF)
    {
      cutoff++;
#ifdef DEBUG
      std::cerr << TABS(dfs_level) << "Immediately return" << std::endl;
#endif
      
      return std::numeric_limits<std::size_t>::max();
    }

  std::size_t best_guarantee;

  if (no_red == 0)
    {
      best_guarantee = pow(2, no_black) * pocket;

#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"Immediately get Best = " << best_guarantee << std::endl;
#endif      
      return best_guarantee;
    }

  if (no_red == 1 && no_black == 1)
    {
      best_guarantee = 2 * pocket;
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"Immediately get Best = " << best_guarantee << std::endl;
#endif      
      return best_guarantee;
    }

  std::size_t cache_guarantee = opt_profit(no_red, no_black, pocket);
  if (cache_guarantee > 0)
    {
      cache_hits++;
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"READ FROM MAP CACHE NoRed = " << no_red << ", NoBlack = " << no_black << ". Pocket = " << pocket << std::endl;
#endif
      return cache_guarantee;
    }

  ++counter;

  if (no_red == no_black)
    // bet nothing, go to subproblem, just pick the branch where a red card is shown
    {
#ifdef DEBUG
      std::cerr << TABS(dfs_level) <<"NoRed = " << no_red << ", NoBlack = " << no_black << ". Decrease NoRed." << std::endl;
#endif 
      return find_opt_profit(no_red - 1, no_black, pocket, dfs_level + 1);
    }

  //return linear_bet_search(no_red, no_black, pocket, dfs_level);
  return binary_bet_search(no_red, no_black, pocket, dfs_level);
}


void
init()
{
  for (std::size_t i = 0; i < MAX_RED; ++i)
    {
      for (std::size_t j = 0; j < MAX_BLACK; ++j)
	{
	  BetMap* bm = new BetMap();
	  betmap[i][j] = bm;
	}
    }
}


int main(int argc, char* argv[])
{
  std::size_t best_guarantee;
  std::size_t no_red;
  std::size_t no_black;
  std::size_t pocket;


  if (argc == 4)
    {
      no_red = std::atoi(argv[1]);
      no_black = std::atoi(argv[2]);
      pocket = std::atoi(argv[3]);
    }
  else
    {
      no_red = 26;
      no_black = 26;
      pocket = 100;
    }

  init();
  best_guarantee = find_opt_profit(no_red, no_black, pocket, 0);

  std::cerr << "CACHE HITS = " << cache_hits << std::endl;
  std::cerr << "CUTOFF = " << cutoff << std::endl;
  std::cerr << "RECURSIVE CALLS = " << counter << std::endl;
  std::cerr << "BEST GUARANTEE  = " << best_guarantee << std::endl;
}
